{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Number of K-Sum Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 和数对的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>每一步操作中，你需要从数组中选出和为 <code>k</code> 的两个整数，并将它们移出数组。</p>\n",
    "\n",
    "<p>返回你可以对数组执行的最大操作数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], k = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>开始时 nums = [1,2,3,4]：\n",
    "- 移出 1 和 4 ，之后 nums = [2,3]\n",
    "- 移出 2 和 3 ，之后 nums = []\n",
    "不再有和为 5 的数对，因此最多执行 2 次操作。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,3,4,3], k = 6\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>开始时 nums = [3,1,3,4,3]：\n",
    "- 移出前两个 3 ，之后nums = [1,4,3]\n",
    "不再有和为 6 的数对，因此最多执行 1 次操作。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= k <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-number-of-k-sum-pairs](https://leetcode.cn/problems/max-number-of-k-sum-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-number-of-k-sum-pairs](https://leetcode.cn/problems/max-number-of-k-sum-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n5', '[3,1,3,4,3]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        sz = len(nums)\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        j = sz - 1\n",
    "        result = 0\n",
    "        while i < j:\n",
    "            a = nums[i]\n",
    "            b = nums[j]\n",
    "            c = a + b\n",
    "            if c < k:\n",
    "                i += 1\n",
    "            elif c > k:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        while True:\n",
    "            if nums and nums[-1] >= k:\n",
    "                nums.pop()\n",
    "            else:\n",
    "                break\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        output = 0\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] == k:\n",
    "                nums.pop(right)\n",
    "                nums.pop(left)\n",
    "                \n",
    "                output += 1\n",
    "                right -= 2\n",
    "            elif nums[left] + nums[right] < k:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        \n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        record = 0\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums) -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > k:\n",
    "                right -= 1\n",
    "            elif nums[left] + nums[right] == k:\n",
    "                del nums[left]\n",
    "                del nums[right-1]\n",
    "                record += 1\n",
    "                right -= 2      \n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        record = 0\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = len(nums) -1\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] < k:\n",
    "                left += 1\n",
    "            elif nums[left] + nums[right] > k:\n",
    "                right -= 1\n",
    "            elif nums[left] + nums[right] == k:\n",
    "                del nums[left]\n",
    "                del nums[right-1]\n",
    "                record += 1\n",
    "                right -= 2      \n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        nums = sorted(nums)\n",
    "        l, r = 0,len(nums) - 1\n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] > k:\n",
    "                r -= 1\n",
    "            elif nums[l] + nums[r] < k:\n",
    "                l += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        cnt = collections.Counter(nums)\n",
    "        ans = 0\n",
    "        for x, c in cnt.items():\n",
    "            ans += min(cnt[k - x], cnt[x])\n",
    "        return ans // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        l, r = 0, n-1\n",
    "        count = 0\n",
    "        while l < r:\n",
    "            print(l, r)\n",
    "            if nums[l] + nums[r] < k:\n",
    "                l +=1\n",
    "            elif nums[l] + nums[r] > k:\n",
    "                r -= 1\n",
    "            else:\n",
    "                count += 1\n",
    "                r -= 1\n",
    "                l += 1\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        for i, v in enumerate(nums):\n",
    "            if v > 2 * k:\n",
    "                right = i\n",
    "                break \n",
    "\n",
    "        res  = 0\n",
    "        while left < right:\n",
    "            if nums[left] + nums[right] == k:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "                res += 1\n",
    "            elif nums[left] + nums[right] > k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "            \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        right = len(nums)-1\n",
    "        for left,num in enumerate(nums):\n",
    "            if left >= right:break\n",
    "            if num + nums[right] == k:\n",
    "                ans += 1\n",
    "                right -= 1\n",
    "            elif num + nums[right] < k:\n",
    "                continue\n",
    "            else:\n",
    "                while left < right and num + nums[right] > k:\n",
    "                    right -= 1\n",
    "                if left < right and num + nums[right] == k:\n",
    "                    ans += 1\n",
    "                    right -= 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        d = Counter(nums)\n",
    "        for x in d:\n",
    "            ans += min(d[x],d[k-x])\n",
    "        return ans //2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        count = Counter()\n",
    "        for num in nums:\n",
    "            if count[k - num]:\n",
    "                count[k - num] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                count[num] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        count = Counter()\n",
    "        for num in nums:\n",
    "            if count[k - num]:\n",
    "                count[k - num] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                count[num] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        dic=Counter(nums)\n",
    "        ans=0\n",
    "        covered=set()\n",
    "        for i in dic:\n",
    "            if i not in covered:\n",
    "                if k-i==i:\n",
    "                    ans+=dic[i]//2\n",
    "                    covered.add(i)\n",
    "                elif k-i in dic:\n",
    "                    ans+=min(dic[i],dic[k-i])\n",
    "                    covered.add(i)\n",
    "                    covered.add(k-i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        stat = defaultdict(int)\n",
    "        for i in nums:\n",
    "            if i<k:\n",
    "                stat[i]+=1\n",
    "        stat = sorted(stat.items(), key=lambda x:x[0])\n",
    "        n = len(stat)\n",
    "        res = 0\n",
    "        record = set()\n",
    "        for i in range(n):\n",
    "            if stat[i][0] in record:\n",
    "                continue\n",
    "            for j in range(n-1,i,-1):\n",
    "                if stat[j][0]==k-stat[i][0]:\n",
    "                    res+=min(stat[i][1],stat[j][1])\n",
    "                    record.add(stat[i][0])\n",
    "                    record.add(stat[j][0])\n",
    "            if stat[i][0]*2==k:\n",
    "                res+=stat[i][1]//2\n",
    "                record.add(stat[i][0])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # res = 0\n",
    "        # n = len(nums)\n",
    "        # nums.sort()\n",
    "        # # print(nums)\n",
    "        # for i in range(n):\n",
    "        #     if nums[i]=='#':\n",
    "        #         continue\n",
    "        #     if nums[i]>=k:\n",
    "        #         break\n",
    "        #     coun = k-nums[i]\n",
    "        #     if coun in nums and coun!=nums[i]:\n",
    "        #         res+=1\n",
    "        #         nums[i]='#'\n",
    "        #         nums[nums.index(coun)]='#'\n",
    "        #     if coun in nums and coun==nums[i]:\n",
    "        #         if nums[i+1]==nums[i]:\n",
    "        #             res+=1\n",
    "        #             nums[i]='#'\n",
    "        #             nums[i+1]='#'\n",
    "        #         else:\n",
    "        #             continue\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans,cnt = 0,Counter(nums)\n",
    "        s = set()\n",
    "        for x in nums:\n",
    "            if x not in s and k-x in cnt:\n",
    "                if x != k-x:\n",
    "                    ans += min(cnt[x],cnt[k-x])\n",
    "                    s.add(k-x)\n",
    "                else:\n",
    "                    ans += cnt[x]//2\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        book = defaultdict(int)\n",
    "        for num in nums:\n",
    "            if book[k - num]:\n",
    "                ans += 1\n",
    "                book[k - num] -= 1\n",
    "            else:\n",
    "                book[num] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        count = Counter(nums)\n",
    "        for num in list(count.keys()):\n",
    "            if k - num:\n",
    "                change = min(count[num], count[k - num])\n",
    "                if num == k - num:\n",
    "                    change //= 2\n",
    "                count[num] -= change\n",
    "                count[k - num] -= change\n",
    "                ans += change\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        i=0\n",
    "        j=len(nums)-1\n",
    "        count=0\n",
    "        while(i<j):\n",
    "            if (nums[i]+nums[j]==k):\n",
    "                count+=1\n",
    "                i+=1\n",
    "                j-=1\n",
    "            elif (nums[i]+nums[j]<k):\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        while nums:\n",
    "            t = nums.pop()\n",
    "            idx = bisect.bisect_left(nums, k-t)\n",
    "            if idx<len(nums) and nums[idx] == k-t:\n",
    "                nums.pop(idx)\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        l,r = 0, len(nums)-1\n",
    "        ans = 0\n",
    "    \n",
    "        while l < r:\n",
    "            if nums[l] + nums[r] == k:\n",
    "                nums[l] = 0\n",
    "                nums[r] = 0\n",
    "                l += 1\n",
    "                r -= 1\n",
    "                ans += 1\n",
    "            elif nums[l] + nums[r] < k:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        for n in nums:\n",
    "            # 如果 n 有可以配对的，则结果加一\n",
    "            if dic.get(k-n,0) >= 1:\n",
    "                res += 1\n",
    "                dic[k-n] -= 1\n",
    "                print(n, k-n)\n",
    "            # 否则，字典中计数加一\n",
    "            else:\n",
    "                if dic.get(n,0) == 0:\n",
    "                    dic[n] = 1\n",
    "                else:\n",
    "                    dic[n] += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        from collections import Counter\n",
    "\n",
    "        c = Counter(nums)\n",
    "\n",
    "        r = [n for n in c.keys() if n < (k+1)//2]\n",
    "        res = sum(min(c[i], c[k-i]) for i in r)\n",
    "        if k % 2 == 0:\n",
    "            res += c[k//2]//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxOperations(self, nums: List[int], k: int) -> int:\n",
    "        n = sorted(nums)\n",
    "        l, r = 0, len(n) - 1\n",
    "        count = 0\n",
    "        while l < r:\n",
    "            if n[l] + n[r] > k:\n",
    "                r -= 1\n",
    "            elif n[l] + n[r] < k:\n",
    "                l += 1\n",
    "            else:\n",
    "                count += 1\n",
    "                r -= 1\n",
    "                l += 1\n",
    "\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
